package demo_leetcode_day;

/*
109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5
*/

public class demo_20200818 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(-10);
        ListNode node2 = new ListNode(-3);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println(new Solution().sortedListToBST(node1));
    }

    static public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            return buildTreeNode(head, null);
        }
        /**
         * 生成树节点
         */
        private TreeNode buildTreeNode(ListNode start, ListNode end){
            if(start == end){
                return null;
            }
            ListNode midNode = getMid(start, end);
            TreeNode root = new TreeNode(midNode.val);
            System.out.println("当前节点:" + root.val);
            root.left = buildTreeNode(start, midNode);
            root.right = buildTreeNode(midNode.next, end);
            return root;
        }
        /**
         * 寻找中间节点
         * 方法：从开始节点开始，使用两个指针，一快一慢，
         */
        private ListNode getMid(ListNode start, ListNode end){
            ListNode fast = start;
            ListNode show = start;
            while (fast != end && fast.next != end){
                // 指针移动
                fast = fast.next;
                fast = fast.next;
                show = show.next;
            }
            // 因为快指针是慢指针2倍速度，当快指针到头时，慢指针就是中间节点
            return show;
        }
    }
}
